//请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(
//1)。 
// 示例： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); 
//minStack.push(-3); minStack.getMin();   --> 返回 -3. minStack.pop(); minStack.top(
//); --> 返回 0. minStack.getMin(); --> 返回 -2. 
//
// Related Topics 栈 设计 👍 104 👎 0


package LeetCode.editor.cn;


import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-06-24 15:22:10
 * @description 面试题 03.02.栈的最小值
 
 */
 
public class MinStackLcci {
    public static void main(String[] args) {
    //测试代码
    MinStackLcci fun = new MinStackLcci();


    }

//leetcode submit region begin(Prohibit modification and deletion)
class MinStack {
        //两种，一种是创建两个栈，一个保存值，一个保存当前位置的最小值
    //一种是直接保存差值，维护一个全局最小的变量,然后出入栈不再用原值，而是差值

    /** initialize your data structure here. */
    long minVal=Integer.MAX_VALUE;
    Deque<Long> st=new ArrayDeque<>();
    public MinStack() {

    }
    /*
    * 计算压入值和当前最小值的差值，如果大于0
    * 说明不是更小的，最小值不更新
    * 否则设置最小值为val
    * */
    public void push(int x) {
        if(st.isEmpty()){
            st.push(0l);
            minVal=x;
        }else {
            long diff=x-minVal;
            st.push(diff);
            minVal=diff>0?minVal:x;
        }
    }
    /*
    * 先看栈顶
    * 如果小于0 ，说明栈顶是最小的，和前面push的过程一样
    * 需要重新计算最小值
    * */
    public void pop() {
        if(!st.isEmpty()){
            long diff=st.pop();
            if(diff<0){
                long res=minVal;
                minVal=minVal-diff;
                return;
            }else {
                long res=minVal+diff;
                return;
            }
        }
    }

    public long top() {
        if(!st.isEmpty()){
            long diff=st.peek();
            return diff<0?minVal:minVal+diff;
        }
        return -1;
    }

    public int getMin() {
        return st.isEmpty()?-1:(int)minVal;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
